/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/rehashing
   @Language: C++
   @Datetime: 16-02-09 08:24
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param hashTable: A list of The first node of linked list
	 * @return: A list of The first node of linked list which have twice size
	 */    
	vector<ListNode*> rehashing(vector<ListNode*> HT) {
		// write your code here
		int cap = HT.size()<<1;
		vector<ListNode*> vs(cap,NULL);
		for(int i=HT.size(); i--;){
			for(ListNode *p=HT[i]; p; p=p->next){
				const int id = (p->val%cap+cap)%cap;
				ListNode *q = vs[id];
				if (q==NULL) vs[id]=new ListNode(p->val);
				else {
					for(; q->next; q=q->next);
					q->next = new ListNode(p->val);
				}
			}
		}
		return vs;
	}
};
